import java.util.Arrays;
/*
    归并排序
 */

public class test44_12_6 {
    public static void main(String[] args) {
        Integer[] arr = {1,5,66,11,9,101,88,-2,100};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(Comparable[] arr){
        Integer left = 0;
        Integer right = arr.length-1;
        sortCpu(left,right,arr);
    }
    public static void sortCpu(Integer left,Integer right,Comparable[] arr){
        if(left>=right)
            return;
        Integer mid = left+(right-left)/2;
        sortCpu(left,mid,arr);
        sortCpu(mid+1,right,arr);
        merge(left,mid,right,arr);
    }

    private static void merge(Integer left, Integer mid, Integer right, Comparable[] arr) {
        Integer p1=left,p2=mid+1,index=left;
        Comparable[] yz = new Comparable[arr.length];
        while (p1<=mid&&p2<=right){
            if(arr[p1].compareTo(arr[p2])<0){
                yz[index++]=arr[p1++];
            }else {
                yz[index++]=arr[p2++];
            }
        }
        while (p1<=mid){
            yz[index++]=arr[p1++];
        }
        while (p2<=right){
            yz[index++]=arr[p2++];
        }
        for (int i = left; i <=right ; i++) {
            arr[i]=yz[i];
        }
    }
}
